/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package auxiliary;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;





/**
 *
 * @author daq
 */
public class RandomForest extends Classifier {
	 int totalTreeNum = 10;
	 int characterNum = 3;
	 Map<Double, List<double[]>> splitedList;
	 List<Node> headNodes;
	    /*
	     * Tree node or leaf
	     */
	    public class Node{
			//attribute numerical:false   attribute discrete:true
			boolean flagCategory;
			//true:smaller; false: not smaller 
			boolean isSmaller;
			//node:0  leaf:1
			int flagNodeLeaf;
			double value;
			double label;
			//classify by the indexth attribute
			int index;
			//children of node
			List<Node> list;
			public Node(){
				flagCategory = false;
				isSmaller = false;
				flagNodeLeaf = 0;
				value = 0;
				label = 0;
				index = 0;
				list = new ArrayList<Node>();
				list.clear();
			}
		}

    public RandomForest() {
    	headNodes = new ArrayList<Node>();
    }

    @Override
    public void train(boolean[] isCategory, double[][] features, double[] labels) {
    	features = fillMissingValue(isCategory, features);
       	List<double[]> list = new ArrayList<double[]>();
       	for(int i = 0; i < features.length; i++){
       		double [] tempDouble = new double[features[i].length + 1];
       		int j = 0;
       		for(; j < features[i].length; j++){
       			tempDouble[j] = features[i][j];
       		}
       		tempDouble[j] = labels[i];
       		list.add(tempDouble);
       	}
       	int createdTrueNum = 0;
       	while(createdTrueNum < totalTreeNum){
       		List<double[]> eachList = bootstrapSamples(list);
       		// the last member of isCategory is for classify or regression
       		Node node = generateTree(isCategory,eachList);
       		headNodes.add(node);
       		createdTrueNum++;
       	}
    }

    @Override
    public double predict(double[] features) {
    	Map<Double,Integer> countLabels = new HashMap<Double,Integer>();
    	for(int i = 0; i < headNodes.size(); i++){
    		Node head = headNodes.get(i);
    		double label = findLabel(head, features);
    		if(countLabels.containsKey(Double.valueOf(label))){
    			Integer num = countLabels.get(Double.valueOf(label));
    			num++;
    			countLabels.remove(Double.valueOf(label));
    			countLabels.put(Double.valueOf(label), num);
    		}else{
    			countLabels.put(Double.valueOf(label), Integer.valueOf(1));
    		}
    	}
    	Iterator<Entry<Double,Integer>> ite = countLabels.entrySet().iterator();
    	double lable = 0;
    	int maxNum = 0;
    	while(ite.hasNext()){
    		Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>) ite.next();
    		int num = entry.getValue().intValue();
    		if(num > maxNum){
    			maxNum = num;
    			lable = entry.getKey().doubleValue();
    		}
    	}
        return lable;
    }

    public double findLabel(Node node, double[] features){
    	if (node.flagNodeLeaf == 1){
    		return node.label;
    	}
   		double property = features[node.index];
    	if (node.flagCategory){
    		for(int i = 0; i < node.list.size(); i++){
    			Node childNode = node.list.get(i);
    			if (property == childNode.value){
    				return findLabel(childNode, features);
    			}
    		}
    	}else{
    		for(int i = 0; i < node.list.size(); i++){
    			Node childNode = node.list.get(i);
    			if (property < childNode.value && childNode.isSmaller){
    				return findLabel(childNode, features);
    			}else if (property >= childNode.value && (!childNode.isSmaller)){
    				return findLabel(childNode,features);
    			}
    		}
    	}
    	return Double.NaN;
    } 
    public List<double[]> bootstrapSamples(List<double[]> list){
    	List<double[]> newList = new ArrayList<double[]>();
    	for(int i = 0; i < list.size(); i++){
    		Random random = new Random();
    		int index = random.nextInt(list.size()-1);
    		newList.add(list.get(index));
    	}
    	return newList;
    }
    
    public int[] randomCharacters(int length){
    	int[] intArray = new int[characterNum];
    	for(int i = 0; i < characterNum; i++){
    		Random random = new Random();
    		int index = random.nextInt(length - 1);
    		for(int j = 0; j < i; j++){
    			if(index == intArray[i]){
    				i--;
    				continue;
    			}
    		}
    		intArray[i] = index;
    	}
    	return intArray;
    }
    
    
    public Node generateTree(boolean[] isCategory, List<double[]> list){
    	Node node;
    	double nodeEntropy = 0;
    	nodeEntropy = getEntropy(list);
    	if(nodeEntropy == 0){
    		node = createLeaf(list);
    		return node;
    	}
    	//the last one of isCategorty indicating classifer or regression
    	int[] indexArray = randomCharacters(isCategory.length - 1);
    	int splitPosition = splitAttribute(indexArray,isCategory, list);
    	if (splitPosition == -1){
    		node = createLeaf(list);
    		return node;
    	}
    	node = new Node();
    	node.flagNodeLeaf = 0;
    	node.flagCategory = isCategory[splitPosition];
    	node.index = splitPosition;

    	double pivot = Double.MAX_VALUE;
    	Iterator<Entry<Double,List<double[]>>> iter = splitedList.entrySet().iterator();
    	if (node.flagCategory == false){
    		while(iter.hasNext()){
    			Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>) iter.next();
    			if (pivot > entry.getKey().doubleValue()){
    				pivot = entry.getKey().doubleValue();
    			}
    		}
    	}
    	Map<Double, List<double[]>> localSplitedList = splitedList;
    	iter = localSplitedList.entrySet().iterator();
    	while(iter.hasNext()){
    		Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>) iter.next();
    		Node childNode = generateTree(isCategory, entry.getValue());
    		if (node.flagCategory){
    			childNode.value = entry.getKey().longValue();
    		}else{
    			childNode.value = pivot;
    			if (pivot < entry.getKey()){
    				childNode.isSmaller = false;
    			}else{
    				childNode.isSmaller = true;
    			}
    		}
    		node.list.add(childNode);
    	}
    	return node;
    }
    

    /**
     * 
     * @param isCategory
     * @param list
     * @param splitedList: for numerical attribute, Left List's key is correct pivot
     * @return
     */
    
   	public int splitAttribute(int[] indexArray,boolean[] isCategory, List<double[]> list){
//       	double entropy = Double.POSITIVE_INFINITY;
       	//TODO
   		double entropy = 0;
   		entropy = getEntropy(list);
       	int splitIndex = -1;
       	for(int pii = 0; pii < indexArray.length; pii++){
       		int i = indexArray[pii];
       		Map<Double, List<double[]>> tempSplitedList = new HashMap<Double, List<double[]>>();
       		tempSplitedList.clear();
     			double tempEntropy = 0;
       		// attribute is discrete
       		if(isCategory[i]){
       			for(int j = 0; j< list.size(); j++){
       				double[] dLine = list.get(j);
       				Double spliteValue = Double.valueOf(dLine[i]);
       				if (tempSplitedList.containsKey(spliteValue)){
       					List<double[]> tempList = tempSplitedList.get(spliteValue);
       					tempList.add(dLine);
       					tempSplitedList.remove(spliteValue);
       					tempSplitedList.put(spliteValue, tempList);
       				}else{
       					List<double[]> temp = new ArrayList<double[]>();
       					temp.add(dLine);
       					tempSplitedList.put(spliteValue, temp);
       				}
       			}
       			Iterator<Entry<Double, List<double[]>>> ite = tempSplitedList.entrySet().iterator();
       			while(ite.hasNext()){
       				Map.Entry<Double, List<double[]>> entry = (Map.Entry<Double, List<double[]>>)ite.next();
       				List<double[]> eachList = entry.getValue();
       				tempEntropy += ((double)eachList.size()) / list.size() * getEntropy(eachList);
       			}
       			if (tempEntropy < entropy && tempEntropy > 0){
       				entropy = tempEntropy;
       				splitIndex = i;
       				splitedList = tempSplitedList;
       			}
       		}else{//attribute is numerical
       			sortByIndexIncrease(i,list);
       			for(int k = 0; k < list.size() - 1; k++){
       				if (list.get(k)[i] == list.get(k+1)[i]){
       					continue;
       				}
       				double pivot = (list.get(k)[i] + list.get(k+1)[i]) / 2;
       				List<double[]> leftList = new ArrayList<double[]>();
       				List<double[]> rightList = new ArrayList<double[]>();
       				for (int j = 0; j <= k; j++){
       					leftList.add(list.get(j));
       				}
       				for (int j = k+1; j < list.size(); j++){
       					rightList.add(list.get(j));
       				}
       				tempEntropy = ((double)leftList.size()) / list.size() * getEntropy(leftList) 
       					+ ((double)rightList.size()) / list.size() * getEntropy(rightList);
       				if (tempEntropy < entropy && tempEntropy > 0){
       					entropy = tempEntropy;
       					splitIndex = i;
       					splitedList = new HashMap<Double,List<double[]>>();
       					splitedList.put(Double.valueOf(pivot), leftList);
       					splitedList.put(Double.valueOf(pivot+1), rightList);
       				}
       			}
       		}
       	}
       	return splitIndex;
       }

    
    public void sortByIndexIncrease(int index, List<double[]> list){
    	double[][] doubleArray = new double[list.size()][list.get(0).length];
    	for (int i = 0; i < list.size(); i++){
    		doubleArray[i] = list.get(i);
    	}
    	for (int i = 0; i < list.size(); i++){
    		for(int j = i+1; j < list.size(); j++){
    			if (doubleArray[i][index] > doubleArray[j][index]){
    				double[] tempForExchange = doubleArray[i];
    				doubleArray[i] = doubleArray[j];
    				doubleArray[j] = tempForExchange;
    			}
    		}
    	}
    	list.clear();
    	for(int i = 0; i < doubleArray.length; i++){
    		list.add(doubleArray[i]);
    	}
    }

    /*
     * create Leaf
     */
    public Node createLeaf(List<double[]> list){
    	Node leaf = new Node();
    	leaf.flagNodeLeaf = 1;
    	Map<Double,Integer> counter = countLabelsNum(list);
    	int maxNum = 0; 
    	Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
    	while(iter.hasNext()){
    		Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
    		if (entry.getValue().intValue() > maxNum){
    			maxNum = entry.getValue().intValue();
    			leaf.label = entry.getKey().longValue();
    		}
    	}
    	return leaf;
    }
    /*
     * counter each labels num in list
     */
    public Map<Double,Integer> countLabelsNum(List<double[]> list){
    	Map<Double,Integer> counter = new HashMap<Double,Integer>();
    	for(int i = 0; i < list.size(); i++){
    		double[] d = list.get(i);
    		Double labels = Double.valueOf(d[d.length-1]);
    		if(counter.containsKey(labels)){
    			Integer num = counter.get(labels);
    			num++;
    			counter.remove(labels);
    			counter.put(labels, num);
    		}else{
    			counter.put(labels, Integer.valueOf(1));
    		}
    	}
    	return counter;
    }
    /*
     * calculte node's entropy
     */
    public double getEntropy(List<double[]> list){
    	Map<Double,Integer> counter = countLabelsNum(list);
    	double result = 0;
    	Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
		while(iter.hasNext()){
			Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
			double p = entry.getValue().doubleValue() / list.size();
			result -= p * (Math.log(p) / Math.log(2));
		}
    	return result;
    }
    /*
     * calculte node's MSE
     * 
     */
    public double getMSE(List<double[]> list){
    	double average = 0;
    	int index = list.get(0).length - 1;
    	for(int i = 0; i < list.size(); i++){
    		average += list.get(i)[index];
    	}
    	average = average / list.size();
    	double mse = 0;
    	double base = 0;
    	for(int i = 0; i < list.size(); i++){
    		base = average - list.get(i)[index];
    		mse += base * base;
    	}
    	mse = mse / list.size();
    	if (mse == 0){
    		double[] d = list.get(0);
    		for (int i = 0; i < d.length; i++){
    		}
    	}
    	return mse;
    }
    /*
     * fill missing values 
     */
     public double[][] fillMissingValue(boolean[] isCategory, double[][] features){
     	Map<Double,Integer> counter = new HashMap<Double,Integer>();
     	List<Integer> missPosition = new ArrayList<Integer>();
     	double sum = 0;
     	for(int i = 0; i < isCategory.length - 1; i++){
     		counter.clear();
     		sum = 0;
     		missPosition.clear();
     		/*
     		 * calculate attributes' sum or times
     		 */
     		for(int j = 0; j < features.length; j++){
     			if (Double.isNaN(features[j][i])){
     				missPosition.add(Integer.valueOf(j));
     				continue;
     			}
     			//attribute is discrete 
     			if (isCategory[i]){
    					if (counter.containsKey(Double.valueOf(features[j][i]))){
    						Integer num = counter.get(Double.valueOf(features[j][i]));
    						num++;
    						counter.remove(features[j][i]);
    						counter.put(Double.valueOf(features[j][i]), num);
    					}else{
    						counter.put(Double.valueOf(features[j][i]), Integer.valueOf(1));
    					}
   				}else{//attribute is numerical
   					sum += features[j][i];
   				}
     		}
     		/*
     		 * fill the missed value
     		 */
    			double filledValue = 0;
     		if(isCategory[i]){
     			int maxNum = -1;
     			Iterator<Entry<Double, Integer>> iter = counter.entrySet().iterator();
     			while(iter.hasNext()){
     				Map.Entry<Double, Integer> entry = (Map.Entry<Double, Integer>)iter.next();
     				Integer value = entry.getValue();
     				if (value.intValue() > maxNum){
     					Double key = entry.getKey();
     					maxNum = value.intValue();
     					filledValue = key.doubleValue();
     				}
     			}
     		}else{
     			int validNum = features.length - missPosition.size();
     			filledValue = sum / validNum;
     		}    		
     		for(int k = 0; k < missPosition.size(); k++){
     				Integer index = missPosition.get(k);
     				features[index.intValue()][i] = filledValue;
     		}
     	}
     	return features;
     }
}
